package cn.z2huo.leetcode.problem.NO_0015;

/*
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
*/

import java.util.*;

public class Solution {
    public List<List<Integer>> threeSum(int[] nums){

        /*Set<Integer> set = new TreeSet();
        for (int i = 0; i < numss.length; i++) {
            set.add(nums[i]);
        }
        Integer[] nums = set.toArray(new Integer[set.size()]);*/

        List<List<Integer>> result = new ArrayList();

        Arrays.sort(nums);

        for (int i = 0; i < nums.length-2; i++) {
            if(i==0 || (i>0 && nums[i]!=nums[i-1])){
                for (int j = i+1; j < nums.length-1; j++) {
                    if(j==i+1 || nums[j]!=nums[j-1]){
                        for (int k = j+1; k < nums.length; k++) {
                            if(nums[i]+nums[j]+nums[k] == 0){
                                result.add(Arrays.asList(nums[i],nums[j],nums[k]));
                            }
                        }
                    }
                }
            }
        }
        return result;
    }

    public void printList(List<List<Integer>> list){
        for(List<Integer> l : list){
            for(Integer i : l){
                System.out.printf("%3d ",i);
            }
            System.out.println();
        }
    }

    public static void main(String[] args){
        Solution solution = new Solution();
//        int[] nums = {-1, 0, 1, 2, -1, -4};
        int[] nums = {-4,-3,-3,0,1,3,5,7};
        solution.printList(solution.threeSum(nums));
    }
}
